◀ Prev · Parts · Full · Next ▶

If f {\displaystyle f} is a bent function on n {\displaystyle n} bits, and α α {\displaystyle \alpha } is any nonzero vector of n {\displaystyle n} bits, then the function that maps x {\displaystyle x} to f ( x ) ⊕ ⊕ f ( x ⊕ ⊕ α α ) {\displaystyle f(x)\oplus f(x\oplus \alpha )} is balanced. The bent functions are exactly the functions for which this is true, for all nonzero choices of α α {\displaystyle \alpha } .cite-ref-szz-3-0[3]

The dictatorship function can be evaluated after examining only a single bit of the input, but that bit must always be examined. Benjamini, Schramm, and Wilson describe a more complex example based on percolation theory with the property that a randomized Las Vegas algorithm can compute the function exactly while ensuring that the probability of reading any particular input bit is small, roughly inversely proportional to the square root of the number of bits.cite-ref-bsw-1-3[1]

◀ Prev · Parts · Full · Next ▶